COUNTING BY CASES

Tags: #◇Computer Science #◇STT101A #◇Conceptual #◇Counting by Cases

---

◇Overview

Counting by Cases ( the Addition Principle / Rule of Sum) decomposes a complex event $E$ into $k$ mutually exclusive and collectively exhaustive subcases $E_1, E_2, \dots, E_k$. Within each case, the Multiplication Rule counts the configurations; across disjoint cases, the counts are summed:
$|E| = |E_1| + |E_2| + \cdots + |E_k|$

◇Key Definitions

• Addition Principle (Rule of Sum): If $E_1, E_2, \dots, E_k$ are pairwise disjoint ($E_i \cap E_j = \emptyset$ for $i \ne j$), then $\left|\bigcup_{i=1}^k E_i\right| = \sum_{i=1}^k |E_i|$.
• Case-Splitting Strategy: Used whenever constraints change depending on an earlier choice (e.g., "at least $k$", "at most $k$", or digit restrictions where $0$ cannot be a leading digit but can be the last digit of an even number).

◇Worked Example

Problem: From $6$ men and $5$ women, a $4$-person committee must have at least $3$ women. How many such committees can be formed?

Solution:
Split into two mutually exclusive cases based on the exact number of women:

• Case 1 (Exactly 3 women and 1 man): $\binom{5}{3} \times \binom{6}{1} = 10 \times 6 = 60$.
• Case 2 (Exactly 4 women and 0 men): $\binom{5}{4} \times \binom{6}{0} = 5 \times 1 = 5$.
• Total: $60 + 5 = 65$.

◇References & Navigation

• Previous Topic: ◇Fundamental Principle of Counting
• Next Topic: ◇Permutations
• Related Notes: ◇Counting Techniques, ◇Combinations